package treeNode;

import java.util.*;

//二叉树前序遍历，遍历方式，利用栈（先进后出） ，先压进去
public class Solution11I {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<Integer>();
        if(root==null){
            return ret;
        }
        Deque<TreeNode> deque = new LinkedList<TreeNode>();
        TreeNode node = root;
        while(!deque.isEmpty()||node!=null){
            while(node!=null){
                ret.add(node.val);
                deque.push(node);
                node = node.left;
            }
            node = deque.pop();
            node = node.right;
        }

        return  ret;
    }

    public static void main(String[] args) {
        /**
         *                 1
         *              /     \
         *             2        3
         *            / \      /  \
         *          3   4     5    6
         *       / \   / \   / \   / \
         *      5  2  3  4  4   3  2 7
         */
        TreeNode root = TreeNodeUtils.getTestTreeNode();
        Solution11I solution = new Solution11I();
        System.out.println(solution.preorderTraversal(root));

    }
}
